package main.java.com.itlin.datastructure.binarysearchtree;

/*
 * java中想实现任意类型可以比较大小     需要实现Comparable接口
 */
public class BSTTree2<T extends Comparable<T>,V> {

    BSTNode<T,V> root;//根节点

    static class BSTNode<T , V>{
        T key;
        V value;
        BSTNode<T,V> left;
        BSTNode<T,V> right;

        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(T key, V value, BSTNode<T,V> left, BSTNode<T,V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }

    /**
     * 查找关键字对应的值
     * @param key - 关键字
     * @return 关键字对应的值
     */
    public Object get(T key){
//        return doGet(root, key);
        return null;
    }



    /**
     * 非递归方式实现查找关键字对应的值
     * @param key - 关键字
     * @return 关键字对应的值
     */
    public V get2(T key){
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        BSTNode<T,V> p = root;
        while(p != null){
            /*
                  -1 key < p.key
                  0  key == p.key
                  1  key > p.key
             */
            int result = key.compareTo(p.key);
            if(result < 0){//
                p = p.left; // 向左找
            }else if(result > 0){
                p  = p.right; // 向右找
            }else {
                return p.value; // 找到了
            }
        }
        return null;

    }

    /**
     * 查找最小关键字对应的值
     * @return 关键字对应的值
     */
    public Object min(){
        return null;
    }

    /**
     * 查找最大关键字对应的值
     * @return 关键字对应的值
     */
    public Object max(){
        return null;
    }

    /**
     * 存储关键字和对应的值
     * @param key
     * @param value
     */
    public void put(int key, Object value){
    }

    /**
     * 查找关键字的前驱值 （比当前元素小的 最大值）
     * @param key - 关键字
     * @return 前驱值
     */
    public Object successor(int key){
        return null;
    }

    /**
     * 查找关键字的后继值 （比当前元素大的最小值）
     * @param key - 关键字
     * @return 后继值
     */
    public Object predecessor(int key){
        return null;
    }

    /**
     * 根据关键字删除
     * @param key - 关键字
     * @return 被删除关键字对应的值  （只删除一个元素）
     */
    public Object delete(int key){
        return null;
    }



}
